package leetcode.code1320;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int minimumDistance(String word) {
		int[][] dist = new int[30][30];
		int[] pos = new int[30];
		for (int i = 0, p = 0; i < 5; i++) {
			for (int j = 0; j < 6; j++) {
				int w1 = i * 6 + j;
				for (int k = 0; k < 5; k++) {
					for (int l = 0; l < 6; l++) {
						int w2 = k * 6 + l;
						dist[w1][w2] = Math.abs(i - k) + Math.abs(j - l);
					}
				}
				pos[p++] = w1;
			}
		}
		char[] cs = word.toCharArray();
		int len = cs.length;
		int[][][] dp = new int[30][30][len + 1];
		for (int i = 0; i < 30; i++) {
			for (int j = 0; j < 30; j++) {
				for (int k = 1; k <= len; k++) {
					dp[i][j][k] = 11 * 400;
				}
			}
		}
		for (int p = 1; p <= len; p++) {
			int w = cs[p - 1] - 'A';
			for (int i = 0; i < 30; i++) {
				for (int j = 0; j < 30; j++) {
					dp[i][w][p] = Math.min(dp[i][w][p], dp[i][j][p - 1] + dist[j][w]);
					dp[w][j][p] = Math.min(dp[w][j][p], dp[i][j][p - 1] + dist[i][w]);
				}
			}
		}
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i < 30; i++) {
			for (int j = 0; j < 30; j++) {
				ans = Math.min(dp[i][j][len], ans);
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(3, this.minimumDistance("CAKE"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
